;; import lists/standard.scm lists/uniq.scm numbers/prime-factorize.scm numbers/modular-exp.scm

(define (lucas m)
  ;; https://en.wikipedia.org/wiki/Lucas_primality_test
  (let* ((m^ (- m 1))
	 (qs (uniq (factor m^))))
    (let loop ((a 1))
      (if (>= a m)
	  'composite
	  (if (= 1 (modular-exp a m^ m))
	      (if (every (lambda (q)
			   (not (= 1 (modular-exp a (quotient m^ q) m))))
			 qs)
		  (cons 'prime a)
		  (loop (+ a 1)))
	      (loop (+ a 1)))))))

(print (lucas 71))
(print (lucas 127))
(print (lucas 2047)) ;; M_11, first non prime mersenne number
(print (lucas 65537))
(print (lucas 1111111111111111111))
